This invention relates to methods and means for detecting and correcting up to t errors in linear cyclic codewords on the fly. More particularly, the invention relates to methods and means for the ultra-fast resolution of t error locations in each affected codeword from a counterpart degree t error locator polynomial, the polynomial being derived from syndromes processed in a data streaming environment such as an optical or magnetic storage subsystem read channel or the like.
Data streaming, Moving Magnetic Storage, and Synchronism
It is well known that applications executing on a multimasking CPU, such as an IBM 390 running under an MVS operating system, can randomly or sequentially update tracks of data recordable on one or more IBM 3390 direct access storage devices (DASDs). The transfers to the DASDs are made via an attached IBM 3990 cache-based staged storage subsystem. The transfer of data between the CPU and the IBM 3990 cache and between the 3990 and any one of the 3390 DASDs are data streaming operations. In this regard, data streaming is a point-to-point uninterrupted movement of data serial by bit or serial by character or codeword in order to achieve high data transfer rates.
It should also be appreciated that a DASD includes a cyclic multitracked magnetic storage medium and an access mechanism. The access mechanism, in turn, includes a writing transducer for mapping the binary digital codewords into time-varying magnetic flux streams onto addressed tracks and a reading transducer for the inverse mapping. Reading a DASD track involves executing an analog-to-digital mapping of the time-varying flux changes created by the magnetized track moving past the read transducer into binary digital codewords. It further involves testing of the codewords as to whether they are the same as those originally recorded. Significantly, the disk storage medium is rotating at a constant angular rate, and this imposes a time constraint on the read path processing. In order for the processing of data copied from the disk to perform as a synchronous system, then t selected actions or events coincide in time. This means that the processing of data copied from the disk must complete the handling of a current codeword in time for the next codeword to be read and processed. That is, the processing must be completed no later than the recorded track image of the next codeword that passes under the DASD read transducer.
Some Attributes of Linear Cyclic Codes, Codewords, and Error Detection
Typically, digital data is written out to DASD tracks as sequences of codewords drawn from a linear block or cyclic error correction code. Upon being read back from DASD, these codewords can be tested for any errors or erasures and corrections made thereto before passing it further on.
Reference should be made to copending Hassner et al. application Ser. No. 08/838,375, filed Apr. 8, 1997, entitled, xe2x80x9cMethod and Means for Computationally Efficient Error and Erasure Correction in Linear Cyclic Codesxe2x80x9d, now U.S. Pat. No. 5,942,005. In the Hassner case, a Reed-Solomon (RS) code is used to exemplify linear cyclic codes. Also, the RS code finds use in communication and storage because it maintains maximum distance among codewords for a given codeword length n. In this regard, the term xe2x80x9cdistancexe2x80x9d means the number of bit changes that must be made to a first codeword such that it would appear to be the same as another codeword in the code set for a given amount of checking overhead.
As Hassner et al. explained, an RS code is one in which every codeword c(z) in an (n,k) linear cyclic code over GF(2m) is generated by dividing a block of data m(z) by a generator polynomial g(z) and adding the remainder thereto to modulo 2. Relatedly, c(z) is a polynomial of degree nxe2x88x921 or less, where
m(z)=m0+M1xc3x971+m2xc3x972+ . . . +m(nxe2x88x92rxe2x88x921)xc3x97(nxe2x88x92rxe2x88x921)
and where g(z)=g0+g1xc3x971+g2xc3x972+ . . . +grxc3x97r, such that c(z)=m(z)/g(z)+remainder. It should be recalled that codewords are conventionally represented as a collection of coefficients of a rational polynomial of an arbitrary place variable z in low-to-high order.
Significantly, a received or read back codeword is r(z)=c(z)+e(z) where c(z) was the codeword originally transmitted or recorded and e(z) is the error. Relatedly, a syndrome polynomial S(z) is informally defined as S(z)=r(z) mod g(z). Thus, r(z)=c(z) if and only if g(z) divides into r(z) with a remainder of zero, i.e., S(z)=0. Otherwise, it can be shown that S(z) is dependent only on the error function e(z) such that S(z)=e(z) mod g(z).
Aspects of Reed Solomon Codes
An RS code may be said to comprise a set of vectors over a finite field F having pm elements, where p is a prime number. The elements of the field F are identified with either of two attributes. That is, they are identified with the pmxe2x88x921 powers of a distinct element xe2x80x9caxe2x80x9d and the symbol xe2x80x9c0xe2x80x9d. Alternatively, they are identified with the set of polynomials of degree of at most mxe2x88x921 and with the coefficients in the field of integers modulo p. For purposes of convenience, let pm=28=256 such that the field F is fixed at F256. In this RS code, all operations are performed modulo 2. The field F256 can be constructed from the primitive polynomial p(z)=z8+z6+z5+z+1 with coefficients in GF(2) and where xe2x80x9caxe2x80x9d is a primitive root of the irreducible polynomial p(z).
The defining property of an RS code C is that all vectors c=(c0, c1, . . . , c254) xcex5 C satisfy the relations for a given set of numbers j:             ∑              k        =        0                    k        =        254              ⁢                  c        k            ⁢              a        jk              =      0    ⁢          xe2x80x83        ⁢    mod    ⁢          xe2x80x83        ⁢          p      ⁡              (        z        )            
In this example, j xcex5 {0,1, . . . , 7}. Also, the positions within a codeword may be indexed by the nonzero elements of the field a0, a1, . . . , a254. That is, c(z)=0 where z=aj.
Illustratively, assume that errors occurred in predetermined positions in a received codeword are indexed by {a5, a13, a28, a29, a124, a136} and the corresponding error values are {a4, a5, a123, a3, a2, a0}. Thus, if a syndrome from the received codeword r is determined from:             ∑              k        =        0                    k        =        254              ⁢                  c        k            ⁢              a        jk              =      0    ⁢          xe2x80x83        ⁢    mod    ⁢          xe2x80x83        ⁢          p      ⁡              (        z        )            
then the nonzero syndromes in the example would be
S0=a86,S1=a235,S3=a45,S4=a205,S5=a239,S6=a113, and S7=a173.
Berlekamp and Horiguchi References
In the prior art as expressed in E. R. Berlekamp, xe2x80x9cAlgebraic Coding Theoryxe2x80x9d, by McGraw-Hill Publishing Co., 1968, pages 178-199, Berlekamp showed that if a linear error correction code had a distance 2t+1 between codewords, then the syndrome S(z) over a codeword c(z) could be expressed formally as the recursion:             ∑              k        =        0                    k        =        254              ⁢                  c        k            ⁢              a        jk              =      0    ⁢          xe2x80x83        ⁢    mod    ⁢          xe2x80x83        ⁢          p      ⁡              (        z        )            
where z is a polynomial presentation of the codeword c(z), w(z) is the error evaluator polynomial, and "sgr"(z) is the error locator polynomial. This has been denominated as the xe2x80x9ckey equationxe2x80x9d. Relatedly, Berlekamp showed that the locations of errors within a received codeword r are determined by the index positions j of aj as the roots of the locator polynomial "sgr"(z)="sgr"(ak)=0. Note, in this specification, the terms xe2x80x9c"sgr"(z)xe2x80x9d and xe2x80x9cƒ(z)xe2x80x9d are used interchangeably to designate the error locator polynomial.
Toshio Horiguchi of NEC Corporation wrote a seminal paper entitled xe2x80x9cHigh Speed Decoding of BCH Codes Using a New Error Evaluation Algorithmxe2x80x9d, published in Electronics and Communications In Japan Part 3, Vol. 72, No. 12, 1989. Scripta Technica, Inc., made an English language translation available in 1990.
In this article, Horiguchi pointed out that decoding and error processing a linear cyclic code, such as a Reed-Solomon (RS) code, requires several broad steps. The first step is that of syndrome determination decoding, while the remaining steps ascertain various factors in the key equation. In the first step, the syndrome set {Sj} is derived. Next, the error locator polynomial "sgr"(z) and the error evaluator polynomial w(z) are computed. This is followed by ascertaining the error locations {lk} using the method of Chien and the computation of the error values {ek} using the method of Forney. Parenthetically, Chien""s method for solving "sgr"(z) was published in an article entitled xe2x80x9cCyclic Decoding Procedures for the BCH Codesxe2x80x9d, IEEE Transactions on Information Theory, Vol. 10, October 1964, pp. 357-363. Likewise, Forney published his mode of estimating w(z) in xe2x80x9cOn Decoding BCH Codesxe2x80x9d, IEEE Transactions on Information Theory, Vol. 11, October 1965, pp. 547-557.
One drawback of the prior art root solvers was reliance on iterative substitution of all values in a finite Galois field to ascertain which would solve the system of equations. Such an approach becomes unmanageable for real-time applications involving high degree polynomials and on-the-fly task completion. This certainly occurs in the synchronous correction of codewords in error streaming from a continuous source.
It is an object of this invention to devise a computationally efficient machine-implementable method and means for detecting and correcting errors and erasures in received codewords on-the-fly within the capacity of a linear cyclic code using ultra-fast error location processing.
It is a related object to devise a machine-implementable method and means where the linear cyclic code is of the Reed-Solomon type, and the received codewords are read back from selected tracks from a moving multitracked magnetic storage device or from a helically tracked optical storage device or the like.
It is yet another object to devise a machine-implementable method and means for ascertaining exact roots for a monic algebraic polynomial equation of low degree in a finite field, and for reducing the number of candidate root values for a polynomial equation of high degree within a finite field, a monic polynomial being a polynomial with a leading coefficient of +1.
The foregoing objects are believed satisfied by a machine-implementable method and means for correcting up to t errors in words defined over a linear cyclic code and received from a communications subsystem or read back from a storage subsystem or the like. In this regard, the code has up to a maximum number of consecutive zero or null values occurring in said code definition. In the method and means, each received word is subject to separate processing for location and value of errors.
More particularly, the method of the invention comprises the steps of deriving one or more syndromes from each received codeword and computing a counterpart error locator polynomial ƒ(z) of degree t from the derived syndromes. Next, the polynomial ƒ(z) is mapped into a canonical form as an augmented matrix M of a system of m linear simultaneous equations in a finite Galois field GF(2m). After this, at least one exact root is extracted as are a subset of the finite Galois field as root candidates. The extraction is attained by a Gaussian Elimination process using selective exponentiation as a linear operator over the Galois field GF(2m). The remaining roots are determined by iteratively substituting the candidates in the system of equations until the equations are satisfied. Lastly, error values are determined from the syndromes at locations in the received word specified by the extracted roots of the counterpart error locator polynomial. Parenthetically, M is an mxc3x97m matrix with entries in GF(2).
Where the error locator polynomial ƒ(z) is of degree (txe2x89xa65), then according to the method and means of this invention, the polynomial could be mapped relatively directly into the augmented matrix M representation of a system of m linear simultaneous equations and all the roots extracted by Gaussian Elimination. That is, for error polynomials expressed as monic algebraic polynomial equations of degree five or less, the mapping of this invention can be executed with limited computation resource. However, where the degree of the error locator polynomial exceeds five, then the output of the Gaussian Elimination is a mix of at least one solution/root and a subset of candidate solutions or roots drawn from the set of all the values in a given-sized finite Galois field. It is then necessary to iteratively substitute the candidate values, noting the ones that constitute solutions. This still constitutes a substantial processing reduction over a trial-and-error search over all possible values for each received codeword in error.
Restated, the method and means of this invention resolve the roots of an error locator polynomial with computational efficiency in order to maintain synchronous data flow of corrected ECC codewords by converting each locator polynomial into a matrix representation of a system of linear equations, including the use of squaring as a linear operation finding the solutions using Gaussian Elimination, exactly for all solutions for low degree polynomials and for higher degree polynomials using the conversion+Gaussian Elimination to resolve some roots and produce a small subset for the remaining candidates from the finite field of interest to iteratively substitute. In virtually all cases, a post-Gaussian Elimination step is required to renormalize the solutions so that they constitute roots of the original error polynomial in time for their use in modifying the codeword being evaluated.